package previous.Test_0208;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
 class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
 }
public class Solution {
     //所有路径
     //全局变量
    List<String> ret;
    public List<String> binaryTreePaths(TreeNode root) {
        ret =new ArrayList<>();
        //路径
        dfs(root,new StringBuilder());
        return ret;
    }
    public void dfs(TreeNode root,StringBuilder _path){
        StringBuilder path=new StringBuilder(_path);
        path.append(Integer.toString(root.val));
        //如果为叶子节点的时候，将其加入到path
        if(root.left==null && root.right==null){
            ret.add(path.toString());
            return;
        }
        //如果不是叶子节点
        path.append("->");
        //剪枝
        if(root.left!=null){
        dfs(root.left,path);
        }
        if(root.right!=null){
        dfs(root.right,path);
        }
    }
    //全排列
    List<List<Integer>> ret1;
    List<Integer> path;
    //实现剪枝
    boolean[] check;
    public List<List<Integer>> permute(int[] nums) {
           ret1=new ArrayList<>();
           path=new ArrayList<>();
           check=new boolean[nums.length];
           dfs(nums);
           return ret1;
    }
    public void dfs(int[] nums){
        //如果path的长度，等于数组长度，这一组排完
        if(path.size()==nums.length){
           ret1.add(new ArrayList<>());
           return;
        }
        for (int i = 0; i < nums.length; i++) {
            if(check[i]==false){
               path.add(nums[i]);
               check[i]=true;
               dfs(nums);
               //回溯
                check[i]=false;
                path.remove(path.size()-1);
            }
        }
    }
    //子集
    List<List<Integer>> ret2;
    List<Integer> path2;
    public List<List<Integer>> subsets(int[] nums) {
         ret2=new ArrayList<>();
         path2=new ArrayList<>();
         int pos=0;
         dfs(nums,pos);
         return ret2;
    }
    public void dfs(int[] nums,int pos){
      ret2.add(new ArrayList<>(path2));
        for (int i = pos; i < nums.length; i++) {
            path2.add(nums[i]);
            dfs(nums,i+1);
            path2.remove(path.size()-1);
        }
    }

 }

